#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 求最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 计算模逆元
int mod_inverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

    if (m == 1) return 0;

    while (a > 1) {
        q = a / m;
        t = m;

        m = a % m;
        a = t;
        t = x0;

        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0) x1 += m0;

    return x1;
}

// 模幂运算
int mod_exp(long long base, int exp, int mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

// RSA 密钥生成
void rsa_keygen(int *n, int *e, int *d) {
    int p = 11597;  // 小素数 p
    int q = 22811;  // 小素数 q
    *n = p * q;  // 模数 n
    int phi = (p - 1) * (q - 1);  // 欧拉函数 φ(n)

    // 公钥 e 的选择
    *e = 65537;  // 常用的公钥指数

    // 私钥 d 的计算
    *d = mod_inverse(*e, phi);
}

// RSA 加密
int rsa_encrypt(int plaintext, int e, int n) {
    return mod_exp(plaintext, e, n);
}

// RSA 解密
int rsa_decrypt(int ciphertext, int d, int n) {
    return mod_exp(ciphertext, d, n);
}

int main() {
    int n, e, d;
    rsa_keygen(&n, &e, &d);

    printf("Public Key: (n = %d, e = %d)\n", n, e);
    printf("Private Key: (n = %d, d = %d)\n", n, d);

    int plaintext = 65560;  // 明文字符 'A'
    printf("Plaintext: %d\n", plaintext);

    int ciphertext = rsa_encrypt(plaintext, e, n);
    printf("Ciphertext: %d\n", ciphertext);

    int decryptedtext = rsa_decrypt(ciphertext, d, n);
    printf("Decrypted Text: %d\n", decryptedtext);

    return 0;
}
